#include<vector>
#include<deque>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
	int findBottomLeftValue(TreeNode* root) {
		if (root == NULL)
			return -1;
		deque<TreeNode*> queue;
		int len = 1;
		int next_len = 0;
		int res = 0;
		queue.push_back(root);
		while (!queue.empty()) {
			res = queue.front()->val;
			while (len > 0) {
				TreeNode* node = queue.front();
				queue.pop_front();
				if (node != NULL && node->left != NULL) {
					queue.push_back(node->left);
					++next_len;
				}
				if (node != NULL && node->right != NULL) {
					queue.push_back(node->right);
					++next_len;
				}
				--len;
			}
			swap(len, next_len);
		}
		return res;
	}
};